import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树类
 * 
 * @author 杨满球（本地）
 *
 */
public class BiTree {
	private BiTreeNode root;

	public BiTree() {
	}

	public BiTree(BiTreeNode root) {
		this.root = root;
	}

	public BiTree(
			Object[] preOrder, Object[] inOrder, int preIndex, int inIndex,
			int count) {
		if (count > 0) {
			Object r = preOrder[preIndex];
			int i = 0;
			for (i = 0; i < count; i++) {
				if (r.equals(inOrder[inIndex + i])) {
					break;
				}
			}
			root = new BiTreeNode(r);
			root.setLeftChild(
					new BiTree(preOrder, inOrder, preIndex + 1, inIndex, i)
							.getRoot());
			root.setRightChild(new BiTree(preOrder, inOrder, preIndex + i + 1,
					inIndex + i + 1, count - i - 1).getRoot());
		}
	}

	public BiTreeNode getRoot() {
		return root;
	}

	public void setRoot(BiTreeNode root) {
		this.root = root;
	}

	/**
	 * 先根遍历(递归)
	 * 
	 * @param n
	 *            根节点
	 * @return 先根遍历树的字符串表示
	 */
	public String preRootTraverse(BiTreeNode n) {
		String str = "";
		if (n != null) {
			str += n.getData().toString();
			str += preRootTraverse(n.getLeftChild());
			str += preRootTraverse(n.getRightChild());
		}
		return str;
	}

	/**
	 * 中根遍历（递归）
	 * 
	 * @param n
	 *            根节点
	 * @return 中根遍历树的字符串表示
	 */
	public String inRootTraverse(BiTreeNode n) {
		String str = "";
		if (n != null) {
			str += inRootTraverse(n.getLeftChild());
			str += n.getData().toString();
			str += inRootTraverse(n.getRightChild());
		}
		return str;
	}

	/**
	 * 后根遍历（递归）
	 * 
	 * @param n
	 *            根节点
	 * @return 后根遍历树的字符串表示
	 */
	public String postRootTraverse(BiTreeNode n) {
		String str = "";
		if (n != null) {
			str += postRootTraverse(n.getLeftChild());
			str += postRootTraverse(n.getRightChild());
			str += n.getData().toString();
		}
		return str;
	}

	/**
	 * 先根遍历
	 * 
	 * @return 先根遍历字符串表示
	 */
	public String preRootTraverse() {
		String str = "";
		BiTreeNode T = root;
		if (T != null) {
			Stack<BiTreeNode> S = new Stack<BiTreeNode>();
			S.push(T);
			while (!S.isEmpty()) {
				T = S.pop();
				str += T.getData().toString();
				while (T != null) {
					if (T.getLeftChild() != null) {
						str += T.getLeftChild().getData().toString();
					}
					if (T.getRightChild() != null) {
						S.push(T.getRightChild());
					}
					T = T.getLeftChild();
				}
			}
		}
		return str;
	}

	/**
	 * 中根遍历
	 * 
	 * @return 中跟遍历字符串表示
	 */
	public String inRootTraverse() {
		String str = "";
		BiTreeNode T = root;
		if (T != null) {
			Stack<BiTreeNode> S = new Stack<BiTreeNode>();
			S.push(T);
			while (!S.isEmpty()) {
				while (S.peek() != null) {
					S.push(S.peek().getLeftChild());
				}
				S.pop();
				if (!S.isEmpty()) {
					T = S.pop();
					str += T.getData().toString();
					S.push(T.getRightChild());
				}
			}
		}
		return str;
	}

	/**
	 * 后跟遍历
	 * 
	 * @return 后跟遍历字符串表示
	 */
	public String postRootTraverse() {
		String str = "";
		BiTreeNode T = root;
		if (T != null) {
			Stack<BiTreeNode> S = new Stack<BiTreeNode>();
			S.push(T);
			boolean flag;
			BiTreeNode p = null;
			while (!S.isEmpty()) {
				while (S.peek() != null) {
					S.push(S.peek().getLeftChild());
				}
				S.pop();
				while (!S.isEmpty()) {
					T = S.peek();
					if (T.getRightChild() == null || T.getRightChild() == p) {
						str += T.getData().toString();
						S.pop();
						p = T;
						flag = true;
					} else {
						S.push(T.getRightChild());
						flag = false;
					}
					if (!flag) {
						break;
					}
				}
			}
		}
		return str;
	}

	/**
	 * 层次遍历
	 * 
	 * @return 层次遍历的字符串表示
	 */
	public String levelTraverse() {
		String str = "";
		BiTreeNode T = root;
		if (T != null) {
			Queue<BiTreeNode> L = new LinkedList<BiTreeNode>();
			L.offer(T);
			while (!L.isEmpty()) {
				T = L.poll();
				str += T.getData().toString();
				if (T.getLeftChild() != null) {
					L.offer(T.getLeftChild());
				}
				if (T.getRightChild() != null) {
					L.offer(T.getRightChild());
				}
			}
		}
		return str;
	}

	/**
	 * 计算树的深度
	 * 
	 * @param T
	 *            根节点
	 * @return 树的深度
	 */
	public int getDepth(BiTreeNode T) {
		if (T == null) {
			return 0;
		} else if (T.getLeftChild() == null && T.getRightChild() == null) {
			return 1;
		} else {
			if (getDepth(T.getLeftChild()) > getDepth(T.getRightChild())) {
				return 1 + getDepth(T.getLeftChild());
			} else {
				return 1 + getDepth(T.getRightChild());
			}
		}
	}
}
